Grokking Meta Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Meta Easy Problems
Toeplitz Matrix (easy)
Solution: Toeplitz Matrix
Remove All Adjacent Duplicates In String (easy)
Solution: Remove All Adjacent Duplicates In String
Minimum Depth of a Binary Tree (easy)
Solution: Minimum Depth of a Binary Tree
Tree Diameter (easy)
Solution: Tree Diameter
Island Perimeter (easy)
Solution: Island Perimeter
Moving Average from Data Stream (easy)
Solution: Moving Average from Data Stream
Move Zeroes (easy)
Solution: Move Zeroes
Missing Ranges (easy)
Solution: Missing Ranges
Palindrome Permutation (easy)
Solution: Palindrome Permutation
Rank Transform of an Array (easy)
Solution: Rank Transform of an Array
Diagonal Traverse (medium)
Solution: Diagonal Traverse
Shortest Path in Binary Matrix (medium)
Solution: Shortest Path in Binary Matrix
Maximum Swap (medium)
Solution: Maximum Swap
Custom Sort String (medium)
Solution: Custom Sort String
Binary Tree Vertical Order Traversal (medium)
Solution: Binary Tree Vertical Order Traversal
Buildings With an Ocean View (medium)
Solution: Buildings With an Ocean View
Basic Calculator II (medium)
Solution: Basic Calculator II
Nested List Weight Sum (medium)
Solution: Nested List Weight Sum
Dot Product of Two Sparse Vectors (medium)
Solution: Dot Product of Two Sparse Vectors
Max Consecutive Ones III (medium)
Solution: Max Consecutive Ones III
Subarray Sum Equals K (medium)
Solution: Subarray Sum Equals K
Next Permutation (medium)
Solution: Next Permutation
Simplify Path (medium)
Solution: Simplify Path
Lowest Common Ancestor of a Binary Search Tree (medium)
Solution: Lowest Common Ancestor of a Binary Search Tree
'K' Closest Points to the Origin (medium)
Solution: 'K' Closest Points to the Origin
Sum of Path Numbers (medium)
Solution: Sum of Path Numbers
Merge Intervals (medium)
Solution: Merge Intervals
Right View of a Binary Tree (medium)
Solution: Right View of a Binary Tree
Number of Islands (medium)
Solution: Number of Islands
Clone Graph (medium)
Solution: Clone Graph
Missing Element in Sorted Array (medium)
Solution: Missing Element in Sorted Array
Number of Substrings Containing All Three Characters (medium)
Solution: Number of Substrings Containing All Three Characters
Capacity To Ship Packages Within D Days (medium)
Solution: Capacity To Ship Packages Within D Days
Count and Say (medium)
Solution: Count and Say
Contiguous Array (medium)
Solution: Contiguous Array
Sliding Window Median (hard)
Solution: Sliding Window Median
Alien Dictionary (hard)
Solution: Alien Dictionary
Minimum Window Substring (hard)
Solution: Minimum Window Substring
Best Meeting Point (hard)
Solution: Best Meeting Point
Maximum Sum of 3 Non-Overlapping Subarrays (hard)
Solution: Maximum Sum of 3 Non-Overlapping Subarrays
Making A Large Island (hard)
Solution: Making A Large Island
Basic Calculator (Hard)
Solution: Basic Calculator
Serialize and Deserialize Binary Tree (hard)
Solution: Serialize and Deserialize Binary Tree
Longest Increasing Path in a Matrix (hard)
Solution: Longest Increasing Path in a Matrix
Valid Palindrome III (hard)
Solution: Valid Palindrome III
Solution: Rank Transform of an Array

Problem Statement

Given an array arr containing integers, replace each element with its rank in the array.

  • The rank is determined based on the size of the element compared to others in the array.
  • Smaller numbers get a lower rank, and equal numbers share the same rank.
  • The ranking starts from 1.

Examples

Example 1:

  • Input: [10, 20, 20, 30]
  • Expected Output: [1, 2, 2, 3]
  • Justification: 10 is the smallest, so its rank is 1. 20, occurring twice, shares the rank 2. 30, being the largest, gets the rank 3.

Example 2:

  • Input: [100, 2, 70, 2]
  • Expected Output: [3, 1, 2, 1]
  • Justification: 2, being the smallest, is ranked 1. 70 is next, so it's ranked 2. 100, the largest, is ranked 3.

Example 3:

  • Input: [5, 5, 5, 5]
  • Expected Output: [1, 1, 1, 1]
  • Justification: All elements are the same, so they all share the same rank, 1.

Solution

To solve this problem, we can leverage sorting and hashmap data structures. The idea is to sort a copy of the original array, which helps in assigning ranks sequentially. We then use a hashmap to store the rank of each unique element from the sorted array. This hashmap acts as a look-up table when we iterate through the original array to replace each element with its corresponding rank. This approach ensures accuracy in ranking and handles duplicate values effectively. It's efficient because sorting and hashmap operations are relatively fast for this kind of task.

Step-by-step Algorithm

  • Create a copy of the original array and sort it. This sorted array will help in assigning ranks.
  • Initialize a hashmap to store the rank of each unique element.
  • Iterate through the sorted array, and for each unique element, assign an increasing rank starting from 1, and store it in the hashmap.
  • Iterate through the original array and replace each element with its rank found in the hashmap.
  • Return the transformed array with ranks.

Algorithm Walkthrough

Using the input [100, 2, 70, 2]:

1. Create Sorted Copy:

  • Input: [100, 2, 70, 2]
  • Sorted Copy: [2, 2, 70, 100]

2. Initialize Hashmap for Ranks:

  • Hashmap: {}

3. Assign Ranks to Unique Elements:

  • Consider 2 (first occurrence), assign rank 1. Hashmap becomes {2: 1}.
  • Encounter 2 again, skip as it's already ranked.
  • Consider 70, assign rank 2. Hashmap becomes {2: 1, 70: 2}.
  • Consider 100, assign rank 3. Hashmap becomes {2: 1, 70: 2, 100: 3}.
  • Final Hashmap: {2: 1, 70: 2, 100: 3}
  • Explanation: Each unique number in the sorted array is assigned a sequential rank starting from 1.

4. Replace Original Array Elements with Ranks:

  • Original: [100, 2, 70, 2]
  • Transformed: [3, 1, 2, 1]

5. Return Transformed Array:

  • Output: [3, 1, 2, 1]

Code

Java
Saved to Cloud

. . . .

Time and Space Complexity Analysis

Time Complexity:

  • The primary operation in these solutions is sorting, which typically has a time complexity of O(n log n), where n is the length of the array.
  • The subsequent operations, such as creating a rank map and transforming the array, have a linear time complexity of O(n).
  • Overall, the time complexity of the algorithm is O(n log n) + O(n), which simplifies to O(n log n).

Space Complexity:

  • Additional space is used for the sorted array and the rank map.
  • The space complexity for storing the ranks is O(u), where u is the number of unique elements in the array.
  • Since the sorted array is a copy of the original array, its space complexity is O(n).
  • Therefore, the total space complexity is O(n) + O(u). In the worst case, if all elements are unique, this simplifies to O(n).
Rank Transform of an Array (easy)
Diagonal Traverse (medium)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-step Algorithm

Algorithm Walkthrough

Code

Time and Space Complexity Analysis

Time Complexity:

Space Complexity: